package srcInterviewPrep;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;

public final class BipartiteChecker
{
    public static boolean IsGraphBipartite(List<Vertex> vertices)
    {
        if (vertices == null)
        {
            throw new IllegalArgumentException("Parameter 'vertices' cannot be null");
        }
        
        HashSet<Vertex> unvisitedVertices = InitializeUnvisitedVertices(vertices);
                
        while (!unvisitedVertices.isEmpty())
        {
            Vertex v = unvisitedVertices.iterator().next();
        
            try
            {
                RunBFS(v, unvisitedVertices);
            }
            catch (NotBipartiteException ex)
            {
                return false;
            }
        }
        
        return true;
    }
    
    private static HashSet<Vertex> InitializeUnvisitedVertices(List<Vertex> vertices)
    {
    	LinkedHashSet<Vertex> hashSet = new LinkedHashSet<Vertex>();
        
        for (Vertex v : vertices)
        {
            hashSet.add(v);
        }
        
        return hashSet;
    }
    
    private static void RunBFS(Vertex v, HashSet<Vertex> unvisitedVertices) throws NotBipartiteException
    {
        Deque<VertexColorPair> nextNodesToVisit = new ArrayDeque<VertexColorPair>();
        nextNodesToVisit.add(new VertexColorPair(v, 0));
        
        Map<Vertex, Integer> visitedNodes = new HashMap<Vertex, Integer>();
        
        while(!nextNodesToVisit.isEmpty())
        {
            VertexColorPair pair = nextNodesToVisit.remove();
            visitedNodes.put(pair.Vertex(), pair.Color());
            
            unvisitedVertices.remove(pair.Vertex());
            
            int nextColor = (pair.Color() + 1) % 2;
            
            for (Vertex n : pair.Vertex().Neighbors())
            {
                if (visitedNodes.containsKey(n))
                {
                    int prevColor = visitedNodes.get(n);
                    if (prevColor != nextColor)
                    {
                        throw new NotBipartiteException();
                    }
                }
                else
                {
                    nextNodesToVisit.add(new VertexColorPair(n, nextColor));
                }
            }
        }
    }
}
